/**
 * 给定⼀个包含 n 个整数的数组 nums 和⼀个⽬标值 target，判断 nums 中是否存在四个元素 a，
    b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满⾜条件且不重复的四元组。
    注意：答案中不可以包含重复的四元组。
    示例：
    给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
    满⾜要求的四元组集合为：
    [
    [-1, 0, 0, 1],
    [-2, -1, 1, 2],
    [-2, 0, 0, 2]
    ]
 */
let fourSum = function(nums, target) {
    nums.sort((a, b) => a - b); //先排序
    const res = [];  //结果数组
    for (let i = 0; i < nums.length - 3; i++) { //第一个数不能是最后三个数
        if(nums[i]>target) break; //当第一个最小值大于target 后面无需再取值了
        for (let j = i + 1; j < nums.length - 2; j++) {
            if(nums[i] + nums[j] > target) break;  //当前两个值大于target 后面无需再取值了
            //双指针 左指针指向第二个值的下一个值开始 右指针从数组最后一个指针开始
            let left = j + 1, right = nums.length - 1;
            while (left < right) {  
                // i ,j 便利循环取前面两个最小的值 ，left right 通过双指针找到两个值，向target靠近
                const sum = nums[i] + nums[j] + nums[left] + nums[right];
                if(sum===target){
                    res.push([nums[i], nums[j], nums[left], nums[right]]);
                    //去重
                    while(nums[left] === nums[left + 1]) left++;
                    while(nums[right] === nums[right - 1]) right--;
                    left++;
                    right--;
                }else if(sum<=target){
                    left++; 
                }else{   
                    right--;
                }
            }
        }
    }
    return res;
}   
console.log(fourSum([ -2, -1, 0,0, 1, 2,3,3,4], 0));

// const myFourSum = (nums, target) => {
//     nums.sort((a, b) => a - b);
//     const res = [];
//     if (nums.length < 4) return res;
//     for(let i =0;i<nums.length-3;i++){
//         for(let j = i+1;j<nums.length-2;j++){
//             for(let k = j+1;k<nums.length-1;k++){
//                 for(let l = k+1;l<nums.length;l++){
//                     if(nums[i]+nums[j]+nums[k]+nums[l]===target){
//                         res.push([nums[i],nums[j],nums[k],nums[l]]);
//                     }
//                 }
//             }
//         }
//     }
//     return res;
// }
// console.log(myFourSum([1,0,-1,0,-2,2],0));